Computers are very powerful tools for storing and providing access to vast amounts of information. Relational databases are a common mechanism for storing information on computer systems while providing easy access to users. A typical relational database is an organized collection of related information stored as “records” having “fields” of information. As an example, a database of employees may have a record for each employee where each record contains fields designating specifics about the employee, such as name, home address, salary, and the like.
Between the actual physical database itself (i.e., the data actually stored on a storage device) and the users of the system, a relational database management system or RDBMS is typically provided as a software cushion or layer. In essence, the RDBMS shields the database user from knowing or even caring about the underlying hardware-level details. Typically, all requests from users for access to the data are processed by the RDBMS. For example, information may be added or removed from data files, information retrieved from or updated in such files, and so forth, all without user knowledge of the underlying system implementation. In this manner, the RDBMS provides users with a conceptual view of the database that is removed from the hardware level. The general construction and operation of database management systems is well known in the art. See e.g., Date, C., “An Introduction to Database Systems, Seventh Edition”, Part I (especially Chapters 1-4), Addison Wesley, 2000.
A key challenge faced by relational database systems is the ever-growing database size. With increasing use of digital devices and ease of data flow on ubiquitous networks, the data explosion has accelerated in recent years. As regular database and table size has grown tremendously in recent years, data compression becomes increasing important even for databases. While row level compression and page level compression for databases have been introduced, a need remains for improved compression techniques to overcome deficiencies in these approaches without causing significant increases in overhead. The present invention addresses this need.